package com.waiting.leetcode;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/21
 **/
public class ConstructBinaryTreeFromInorderAndPostorderTraversal106 {
    public static void main(String[] args) {

    }

    //    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        if (inorder == null || postorder == null) {
//            return null;
//        }
//        int rootVal = postorder[postorder.length - 1];
//        TreeNode root = new TreeNode(rootVal);
//        int rootValIndex = -1;
//        for (int i = 0; i < inorder.length; i++) {
//            if (inorder[i] == rootVal) {
//                rootValIndex = i;
//                break;
//            }
//        }
//        if (rootValIndex != -1) {
//            root.left = ite(inorder, postorder, 0, rootValIndex - 1);
//        }
//        return root;
//    }
//
//    public TreeNode ite(int[] inorder, int[] postorder, int start, int end) {
//        if (start == end) {
//            return new TreeNode(inorder[start]);
//        } else {
//
//        }
//    }
    public int search(int[] inorder, int val) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

    public TreeNode createBST(int[] inorder, int[] postorder, int st, int end) {
        if (st > end) {
            return null;
        }
        int val = postorder[postOrderIndex];

        TreeNode root = new TreeNode(val);
        postOrderIndex--;
        int index = search(inorder, val);
        root.right = createBST(inorder, postorder, index + 1, end);
        root.left = createBST(inorder, postorder, st, index - 1);

        return root;
    }

    int postOrderIndex = 0;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postOrderIndex = postorder.length - 1;

        int st = 0;
        int end = postorder.length - 1;

        TreeNode root = createBST(inorder, postorder, st, end);

        return root;
    }

}
